12. טרנספורמציות פורייר מהירות
מבנה
נתונים ואלגוריתמים
לטרנספורמציות
פורייר יש טווח יישומים רחב בבעיות מדעיות והנדסיות. לדוגמא, בטרנספורמציות אלו
נעשה שימוש נרחב בעיבוד אותות, כדי להעביר אותות מתחום של זמן לתחום של תדירות.
כאן נתייחס לשימוש
שנעשה בהן כדי להגיע לפתרון יעיל לבעיה אשר לכאורה אינה קשורה - הכפלת שני
פולינומים. מלבד ההדגמה כיצד אלגוריתם של טרנספורמציית פורייר מהירה (FFT - Fast Fourier Transform) טרנספורמציות מחשב
טרנספורמציית פורייר מסוימת ומספק את זמן הסיבוכיות שלה, גישה זו גם מחזקת באופן
כללי את הנקודות הבאות:
·
פתרונות
"טובים" יותר קיימים לבעיות רבות, אשר באופן אינטואיטיבי לא נראה כי
ניתן למצוא להן פתרונות כאלה.
·
כתוצאה מכך,
כאשר אין לאדם מידע נרחב בתחום של בעיה כלשהי, רצוי כי הוא ייעזר בספרות לפני
שינסה לפתור בעיה מספרית או בעיה של עיבוד נתונים.
בגלל מגבלות HTML בטיפול במשוואות מתמטיות, ההערות של חלק זה נעשו בעזרת LaTeX והן זמינות כקובץ PostScript